Çalışma Soruları

1) Aşağıdaki verilen graf türlerinin genel özelliklerini açıklayınız.

a) Tamamlanmış graf b) Düzenli graf c) Düzlemsel graf

2) Aşağıdaki verilen kavramları/tanımları graf veri modeli için açıklayınız.

a) Yol b) Dolaşı c) Gezi

3) Graf veri modelinin matematiksel tanımı nasıl yapılmaktadır. Bir örnek üzerinde göstererek açıklayınız.

4) Grafların bellek üzerinde tutulması için birçok yol vardır. Bunlar genel olarak matris üzerinde, bağlantılı listeyle veya dizili-bağlantılı liste şeklinde sınıflanabilmektedir. Her üç yöntemi bellek gereksinimi açısından karşılaştırınız. Hangi durumlarda hangisinin tercih edilebileceğini açıklayınız.

5) Matris üzerinde tutulan N düğümlü bir K grafının tam bağlı graf olup olmadığını sınayan ve tam bağlı ise 0, değilse eksi bir tamsayı gönderen bir C fonksiyonu tasarlayınız. Fonksiyona aktarılan parametre grafın adı olup dönüş değeri bir tamsayıdır.

6) Bir üniversitede adları d0, d1, d2, d3 ve d4 olan 5 tane ders ve toplam 6 tane öğrenci vardır. Herbir öğrencinin aldığı dersler ise aşağıdaki gibidir:

Öğrenci-1 Öğrenci-2 Öğrenci-3 Öğrenci-4 Öğrenci-5 Öğrenci-6
d0, d2, d4 d0, d4 d1, d2, d4 d3, d4 d3 d2, d3, d4

Bu verilere göre, final sınavında herhangi bir öğrencinin sınavı çakışmayacak şekilde yerleştirim yapılabilmesi için aynı anda yapılabilecek derslerin hangileri olduğunu belirleyiniz. Tüm derslerin sınavını yapabilmek için kaç farklı oturum yapılması gerekir?

7) Veri yapısı aşağıdaki gibi verilen ve bit düzeyinde tutulan 4-düğümlü bir grafın iki düğüme arasında bir kenar olup olmadığını sınayan kenarVarmi() adlı bir C fonksiyonu tasarlayınız.

struct satir {
         unsigned A:1, B:1, C:1, D:1;
};

struct A {
        struct satir A[4];
};

8) Önce derinlik sınaması (DFS) ve önce genişlik sınması (BFS) graf üzerinde dolaşma yapılması için iki temel yaklaşımdır. İkisi arasındaki farkı açıklayınız ve bir örnek graf üzerinde gösteriniz.